#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

// Dijkstra算法模版（Leetcode）
// 网络延迟时间
// 有 n 个网络节点，标记为 1 到 n
// 给你一个列表 times，表示信号经过 有向 边的传递时间
// times[i] = (ui, vi, wi)，表示从ui到vi传递信号的时间是wi
// 现在，从某个节点 s 发出一个信号
// 需要多久才能使所有节点都收到信号
// 如果不能使所有节点收到信号，返回 -1
// 测试链接 : https://leetcode.cn/problems/network-delay-time

    // 动态建图 + 普通堆的实现
class Solution 
{
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) 
    {
        vector<vector<pair<int, int>>> g(n);
        for(auto& t : times)
        {
            // 将坐标转换成 0 ~ n - 1
            int x = t[0] - 1, y = t[1] - 1, w = t[2];
            g[x].push_back({y, w});
        }

        const int INF = 0x3f3f3f3f; // 无穷大
        vector<int> dist(n, INF);
        dist[k - 1] = 0;
        vector<bool> visited(n);
        // first：原点到当前点的距离，second：当前节点
        // 这样做的目的是可以利用库中实现的比较器，不用自己重新实现
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
        q.push({0, k - 1});
        while(!q.empty())
        {
            int x = q.top().second;
            q.pop();
            if(visited[x]) continue;
            
            visited[x] = true;
            for(auto& [y, w] : g[x])
            {
                if(!visited[y] && dist[y] > dist[x] + w)
                {
                    dist[y] = dist[x] + w;
                    q.push({dist[y], y});
                }
            }
        }
        
        int ret = *max_element(dist.begin(), dist.end());
        return ret == INF ? -1 : ret;
    }
};

// 链式前向星 + 反向索引堆的实现
class Solution 
{
private:

    const int INF = 0x3f3f3f3f; // 无穷大
    const int MAXN = 101; // 点的最大数量
    const int MAXM = 6001; // 边的最大数量
    int cnt = 1; // 边的编号
    int heapSize = 0; // 堆中元素的个数

    // 链式前向星
    vector<int> head;
    vector<int> next;
    vector<int> to;
    vector<int> weight;

    vector<int> dist; // 保存原点到各点的距离
    vector<int> heap; // 堆中存的是节点 i

    // where[i] = -1：节点 i 没有进过堆
    // where[i] = -2：节点 i 从堆中弹出过
    // where[i] >= 0：节点 i 在堆中的位置
    vector<int> where; // 记录节点在堆中的位置

    // 链式前向星初始化
    void build(int n)
    {
        cnt = 1;
        heapSize = 0;

        // 这里可以 resize 成 MAXN 也行
        dist.resize(n + 1, INF);
        where.resize(n + 1, -1);
        heap.resize(n + 1);

        head.resize(MAXN);
        next.resize(MAXM);
        weight.resize(MAXM);
        to.resize(MAXM);
    }

    // 链式前向星加边
    void addEdge(int u, int v, int w)
    {
        next[cnt] = head[u];
        to[cnt] = v;
        weight[cnt] = w;
        head[u] = cnt++;
    }

    void addOrUpdateOrIgnore(int v, int c)
    {
        // 节点 v 没有进过堆
        if(where[v] == -1)
        {
            heap[heapSize] = v;
            where[v] = heapSize++;
            dist[v] = c;
            heapInsert(where[v]);
        }
        else if(where[v] >= 0)
        {
            // 节点 v 进入过堆，尝试去更新到 v 的最短距离
            dist[v] = min(dist[v], c);
            heapInsert(where[v]);
        }
        // where[v] == -2：节点 v 从堆中弹出过，说明到 v 的最短距离已经求出来了，直接忽略
    }

    // 向上调整算法
    void heapInsert(int i)
    {
        while(dist[heap[i]] < dist[heap[(i - 1) / 2]])
        {
            swap(i, (i - 1) / 2);
            i = (i - 1) / 2;
        }
    }

    void swap(int i, int j)
    {
        int tmp = heap[i]; // 节点 tmp
        heap[i] = heap[j];
        heap[j] = tmp;
        where[heap[i]] = i;
        where[heap[j]] = j;
    }

    bool isEmpty()
    {
        return heapSize == 0;
    }

    int pop()
    {
        int ans = heap[0];
        swap(0, --heapSize);
        heapify(0); // 向下调整算法
        where[ans] = -2;
        return ans;
    }

    void heapify(int i)
    {
        int l = 2 * i + 1;
        while(l < heapSize)
        {
            int best = l + 1 < heapSize && dist[heap[l + 1]] < dist[heap[l]] ? l + 1 : l;
            best = dist[heap[best]] < dist[heap[i]] ? best : i;
            if(best == i) break; // 孩子没有比父亲小的
            swap(best, i); // 较小的孩子和父亲交换
            i = best; // 父亲来到孩子的位置
            l = 2 * i + 1; // 下一个要比较的孩子
        }
    }

public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) 
    {
        build(n);
        for(auto& e : times)
        {
            addEdge(e[0], e[1], e[2]);
        }

        addOrUpdateOrIgnore(k, 0);
        while(!isEmpty())
        {
            int u = pop();
            for(int ei = head[u]; ei > 0; ei = next[ei])
            {
                addOrUpdateOrIgnore(to[ei], dist[u] + weight[ei]);
            }
        }
        
        // 注意：这里的节点编号是 1 ~ n，所以不需要考虑 dist[0]
        int ret = *max_element(dist.begin() + 1, dist.end());
        return ret == INF ? -1 : ret;
    }
};